A typical data communications network includes multiple host computers that are linked together by a combination of data communications devices and transmission media. In general, the host computers communicate by (i) packaging data using a standardized protocol or format such as a network packet or cell (hereinafter generally referred to as a packet), and (ii) exchanging the packaged data through the data communications devices and transmission media.
In some networks, the packaged data is classified into different Quality of Service (QoS) classes that dictate how competing traffic flows are provided resources. Such resource allocation affects how quickly the packaged data travels from a source to a destination. For example, a distinction may be drawn between packets carrying video data (i.e., video packets belonging to a video QoS class) and packets carrying general data (i.e., general data packets belonging to a general data QoS class such as Best Effort Service). In this arrangement, a data communications device routes video packets through a network differently than general data packets due to different link resource availability and resources being allocated differently based on the QoS class of the packets.
There are different types of QoS routing techniques. In one QoS routing technique (hereinafter called QoS class-prioritized routing), a data communications device internally prioritizes the processing of different QoS class packets in accordance with a pre-established QoS policy. For example, in accordance with one such QoS policy, a data communications device gives higher priority to video packets relative to general data packets. Accordingly, if the data communications device simultaneously receives a video packet and a general data packet (e.g., through multiple input ports), the QoS policy directs the device to process the video packet before the general data packet. As a result, in QoS class-prioritized routing, packet destinations (i.e., receiving host computers) generally perceive different responses, or Qualities of Service, for different QoS classes (e.g., faster video transmissions than general data transmissions).
In another QoS routing technique (hereinafter called load-directed routing), the data communications device generally directs packets through the network based on network load conditions. For example, suppose that the data communications device has multiple output ports to data paths that eventually lead to the same remote destination (i.e., the same receiving host computer). When the data communications device receives a video packet destined for that remote destination, the device transmits the video packet out the output port expected to lead to a low traffic area of the network. On the other hand, when the device receives a general data packet destined for the same remote destination, the device transmits the general data packet out a different output port expected to lead to a high traffic area of the network. With this arrangement, the video packet should travel through the network faster than the general data packet. Accordingly, the load-directed routing technique generally provides the same result as the QoS class-prioritized routing technique. That is, packet destinations (i.e., receiving host computers) generally perceive different Quality of Service or responses for different QoS classes (e.g., quicker video transmissions than general data transmissions).
In contrast to conventional quality of service (QoS) routing techniques that route data exclusively based on a QoS policy, or that route data exclusively based on load-balancing criteria, the invention is directed to techniques for routing data in a manner that simultaneously satisfies a QoS policy constraint, and a network efficiency constraint (e.g., load balancing). That is, embodiments of the invention provide load-balancing while, at the same time, satisfying QoS requirements.
One technique involves obtaining data from a network using a data communications device having multiple output ports. This technique further involves choosing one of the output ports based on an associated quality of service of the data, a pre-established QoS policy, and network efficiency information. The technique then involves transmitting the data to the network through the chosen output port. Accordingly, the technique satisfies both a QoS policy constraint as well as a network efficiency constraint.
Preferably, the data resides in a packet having a source field, a destination field and a QoS field. In this situation, the device scans the source and destination fields to determine the source and intended destination (e.g., host computers) of the packet. Alternatively, only the destination and QoS fields are used. Similarly, the device scans the QoS field of the packet to determine the associated QoS of the data. The associated QoS may be in the form of a number identifying a particular QoS class, a delay bound indicating a limit on the amount of time permitted for the data to travel from its source to its destination, a bandwidth requirement, a combination of such criteria or other criteria.
In one particular technique, the network efficiency information includes network load information describing network load conditions at the output ports of the data communications device. In one embodiment, the network load information is gathered and distributed among data communication devices within the network. That is, the data communications device that operates in accordance with the invention receives the network load information from neighboring devices that observe the local network environment. Alternatively, the network load information is acquired from traffic monitors that observe network traffic at the output ports.
With the network load information, the data communications device chooses one of the multiple output ports of the data communications device for data transmission. First, a policy stage of the data communications device selects, from a set of available network paths extending from the device, a set of QoS policy compliant network paths based on the associated QoS class of the data and the pre-established QoS policy. Next, using the network load information as a load distribution constraint, an efficiency stage of the device identifies one of the policy compliant network paths based on the associated QoS of the data and the network load information. The chosen output port is an output port through which the identified one of the set of policy compliant network paths passes.
It should be understood that each of the policy compliant network paths preferably extends from the data communications device to a designated destination identified by the destination field of the packet. Furthermore, each policy compliant network path preferably is capable of carrying the data (e.g., formatted as a packet) in accordance with the associated QoS of the packet.
Furthermore, for the above-described particular technique, it should be understood that the modularization of the data communications device""s operation into a policy stage and an efficiency stage adds flexibility to the device. For example, one pre-established policy can be substituted with another in the policy stage without interfering with the operation of the efficiency stage. Similarly, different load balancing rules can be imposed in the efficiency stage without interfering with the operation of the policy stage. Accordingly, various policy and load balancing algorithms can be incorporated in the data communications device in order to optimize and customize its operation.
A thorough explanation of particular QoS policies and routing algorithms that are suitable for use by the invention are described in a thesis entitled, xe2x80x9cQuality-of-Service Routing in Integrated Services Networks,xe2x80x9d by Qingming Ma, published May, 1999 (although dated January, 1998), Carnegie Mellon University, Pittsburgh, Pa., CMU-CS-98-138, the teachings of which are hereby incorporated by reference in their entirety.
Preferably, the data communications device receives the pre-established QoS policy from another data communications device in the network prior to choosing the output port. In particular, such a QoS policy preferably is conveyed through the transmission media linking the devices together within the network.
It should be understood that not every packet having an associated QoS needs to be routed in the above described manner. Rather, the data communication device preferably transmits packets of a best effort class through a predetermined output port without regard for the pre-established policy and the network efficiency information. For a packet of the best effort class, there is no guarantee that the packet will be delivered to its designated destination.
Similarly, according to one embodiment of the invention, for a packet that belongs to pre-established packet stream, the data communications device transmits the packet through a predetermined output port without regard for the pre-established policy and the network efficiency information.
It should be further understood that the choice of output ports can be based on other criteria as well as those identified above. For example, in one embodiment, the choice of output port is based further on network topology information including adjacent hop data and propagation delay data. Such other criteria can be imposed in different operating stages of the data communications device due to its modularity. For example, the topology criteria can be combined with the pre-established QoS policy within the policy stage. Alternatively, the topology criteria can be combined with load balancing rules in the efficiency stage. As another alternative, a separate topology criteria stage can be added. Accordingly, data communications devices configured in accordance with the invention provide improved flexibility for incorporating routing criteria that is superior to conventional devices that operate exclusively based on a QoS class-policy or exclusively based on load-balancing criteria.
One embodiment of the invention is directed to a computer program product that includes a computer readable medium having instructions stored thereon for routing data in a computerized data communications device having multiple output ports. The instructions, when processed by the computerized data communications device, cause the computerized data communications device to perform the steps of: obtaining data from a network, the data having an associated quality of service; choosing one of the multiple output ports of the data communications device based on the associated quality of service of the data, a pre-established policy, and network efficiency information for the multiple output ports; and, transmitting the data to the network through the chosen one of the multiple output ports.